Digital cameras are steadily increasing in popularity due to their declining costs, which make them well within the reach of the average consumer. In order to keep costs low, many color digital cameras are single-sensor digital cameras in which only a single image sensor is used to capture color information for each pixel in a color image. Each image sensor in a single-sensor digital camera, which is typically a charge-coupled device (CCD) or a complementary metal oxide semiconductor (CMOS), is part of a sensor array that represent the pixels of a color image. Each image sensor can only generate information about a single color at a given pixel. A color image, however, is represented by combining three separate monochromatic images. In order to display a color image, all of the red, blue and green (RGB) color values are needed at each pixel. In an ideal (and expensive) camera system, each pixel in the sensor array would be provided with three image sensors, each one measuring a red, green or blue pixel color. In a single-sensor digital camera, however, only a single red, blue or green color value can be determined at a given pixel. In order to obtain the other two missing colors, a technique must be used to estimate or interpolate the missing colors from surrounding pixels in the image.
Estimating or interpolating missing colors as discussed above is called “demosaicing”. The “demosaicing” term is derived from the fact that a color filter array (CFA) is used in front of the image sensors, with the CFA being arranged in a mosaic pattern. This mosaic pattern has only one color value for each of the pixels in the image. In order to obtain the full-color image, the mosaic pattern must be “demosaiced”. Thus, demosaicing is the technique of interpolating back from the image captured with a mosaic-pattern CFA, so that a full RGB value can be associated with every pixel. More specifically, a single-sensor digital camera captures the image using an image sensor array that is preceded in the optical path by a CFA. A highly common mosaic CFA is called the Bayer mosaic pattern. The Bayer mosaic pattern (or Bayer filter) is shown in FIG. 1. For each 2×2 set of pixels, two diagonally opposed pixels have green filters, and the other two pixels have red and blue filters. Since the color green (G) carries most of the luminance information for humans, its sampling rate is twice that of the color red (R) and the color blue (B).
There are multitudes of demosaicing techniques available. One of the simplest approaches to demosaicing is bilinear interpolation. In general, bilinear interpolation uses three color planes that are independently interpolated using symmetric bilinear interpolation. This interpolation uses a pixel's nearest neighbors having the same color as the color that is being interpolated. In particular, referring again to FIG. 1, in bilinear interpolation the green value g(i,j) at a pixel position (i,j) that falls in a red or blue pixel is computed by the average of the neighboring green values in a cross pattern, as follows,
                                          g            ^                    ⁡                      (                          i              ,              j                        )                          =                                            1              4                        ⁢                                          ∑                                                                                                                                ⁢                                                          ⁢                                                g                  ⁡                                      (                                                                  i                        +                        m                                            ,                                              j                        +                        n                                                              )                                                  ⁢                                  (                                      m                    ,                    n                                    )                                                              =                      {                                          (                                  0                  ,                                      -                    1                                                  )                            ,                              (                                  0                  ,                  1                                )                            ,                              (                                                      -                    1                                    ,                  0                                )                            ,                              (                                  1                  ,                  0                                )                                      }                                              (        1        )            Equation (1) corresponds to estimating the green value at the pixel marked ‘X’ (also called the “current pixel”) in FIG. 1 as the average of the observed green values marked ‘o’. It should be noted that the current pixel has a red color, and therefore the green and blue color values need to be interpolated. At image boundaries, only pixels that fall within the image are included, and the scaling adjusted.
Bilinear techniques typically use a small region of support. The region of support is the size of a pixel neighborhood whose values are considered for the interpolation of any given pixel. The region of support for the bilinear interpolation techniques described below typically is a 3×3 pixel region of support. Using this small of a region of support keeps memory usage and computational complexity to a minimum.
One problem, however, with many bilinear interpolation techniques is that they generate significant artifacts in the color image. This is especially true across edges and other high-frequency content in the image, since bilinear interpolation does not consider the statistical correlation among RGB values. Thus, while bilinear interpolation techniques are fast, computationally non-intensive, and easy to implement, they are also notorious for producing low-quality images due to the significant artifacts (mainly blurriness and color fringing) that they generate.
Better, though more complex, interpolation techniques take the correlation among RGB values into account. One group of interpolation techniques consider such correlation by using improved linear filters. For example, such a technique is described in a paper by S.-C. Pei and I.-K. Tam entitled “Effective color interpolation in CCD color filter array using signal correlation,” in Proc. ICIP, pp. 488-491, September 2000 [4]. Another group of interpolation techniques consider such correlation by using nonlinear filters. These nonlinear filters essentially adapt interpolation smoothness to a measure of image activity or edginess. For example, these nonlinear interpolation techniques are discussed in the following papers: (1) P. Longére, X. Zhang, P. B. Delahunt, and D. H. Brainard, “Perceptual assessment of demosaicing algorithm performance,” Proc. IEEE, vol. 90, pp. 123-132, January 2002 [1]; and (2) R. Ramanath, W. E. Snyder, and G. L. Bilbro, “Demosaicking methods for Bayer color arrays,” J. Electronic Imaging, vol. 11, pp. 306-315, July 2002 [2].
Exploiting correlation among RGB channels is the main idea behind improving demosaicing performance in nonlinear interpolation techniques. Specifically, it can be assumed that in a luminance/chrominance decomposition, the chrominance components do not vary much across pixels. In a constant-hue approach described in U.S. Pat. No. 4,724,395 to Freeman entitled, “Median filter for reconstructing missing color samples”, the green channel is bilinearly interpolated and then the red and blue channels are interpolated so as to maintain a constant hue, defined as the R/G and B/G ratios. However, one problem with this technique by Freeman is that even at the expense of computing these ratios, the technique still produces visible artifacts. Moreover, using complex operations (such as division and multiplication) in the computing of interpolations greatly increases the computational complexity, processing overhead, and implementation cost.
Improved results for nonlinear interpolation techniques can be obtained by starting with bilinearly interpolated green pixels and then applying median filters to the interpolated values of the color differences R−G and B−G. Improved performance can be obtained by using gradient-based nonlinear techniques, which typically estimate edge directions and adjust the interpolation formulas so that filtering is performed preferentially along edge directions, and not across them. For example, one gradient-based nonlinear technique is described in U.S. Pat. No. 5,373,322 to C. A. Laroche and M. A. Prescott entitled “Apparatus and method for adaptively interpolating a full color image utilizing chrominance gradients”. The Laroche and Prescott technique first interpolates the green channel by using both the red and blue channels to determine edge directions, which determine unequal weights to the terms in equation (1) for the green channel. The color differences R−G and B−G then are interpolated. This technique is disadvantageous in that two computational passes are required to compute the missing color data in the image. A technique described in U.S. Pat. No. 5,506,619 to J. E. Adams and J. F. Hamilton, Jr., entitled “Adaptive color plane interpolation in a single color electronic camera” improves on the Laroche and Prescott technique by considering both first and second order pixel differences (see also J. E. Adams, “Design of practical color filter array interpolation algorithms for digital cameras,” Proc. SPIE, vol. 3028, pp. 117-125, February 1997) [7]. Again, Adams and Hamilton's technique, and most other non-linear interpolation methods, interpolate the green pixel values first and then use these green values to interpolate the blue and red values. This requires two passes of the image in order to interpolate all red, green and blue color values which greatly increases the time necessary to interpolate the missing colors in an image.
A technique described in a paper by E. Chang, S. Cheung, and D. Y. Pan, entitled “Color filter array recovery using a threshold-based variable number of gradients,” in Proc. SPIE, vol. 3650, pp. 36-43, Jan. 1999 [8], is an improvement on the above techniques by considering a variable number of gradients. A simpler but efficient algorithm that uses soft decision rules to combine interpolation results from horizontal and vertical directions is presented in a paper by X. Wu and N. Zhang, entitled “Primary-consistent soft-decision color demosaic for digital cameras,” in Proc. ICIP, vol. I, pp. 477-480, September 2003 [9].
Iterative methods can lead to further improvement by using results from blue and red interpolations to correct the green interpolation, and vice-versa. That is the basis of a technique described in a paper by R. Kimmel, “Demosaicing: image reconstruction from color CCD samples,” IEEE Trans. on Image Processing, vol. 8, pp. 1221-1228, September 1999 [3]. In Kimmel's approach, the interpolation steps are based on a combination of the constant-hue and gradient-based methods. A more recent technique introduced by Lukac et. al [11] also uses correction steps. A technique based on iterative projections is presented in a paper by B. K. Gunturk, Y. Altunbasak, and R. M. Mersereau, entitled “Color plane interpolation using alternating projections”, in IEEE Trans. on Image Processing, vol. 11, pp. 997-1013, September 2002 [6]. The Gunturk technique has the best performance to date on a popular set of standard test images. One problem, however with the Gunturk technique is that it has a very high complexity (as many as 480 operations per input pixel). Additionally, more than one pass across the image is required to interpolate the red, green and blue pixel values, making this technique slow and computationally inefficient.
The above-described nonlinear interpolation techniques typically use a larger region of support that is used in bilinear interpolation techniques. For example, a 5×5 pixel region of support is typical for these nonlinear techniques. A 5×5 region of support yields good correlation between RGB values and produce high-quality images. A smaller region of support greatly reduces the image quality, while larger regions of support require more memory and greatly increase computational complexity.
In a paper by H. S. Malvar, L.-W. He, and R. Cutler entitled “High-quality linear interpolation for demosaicing of Bayer-patterned color images”, Proc. ICASSP, Montreal, Canada, vol. 3, pp. III-485-488, May 2004 [10] and in a co-pending patent application entitled “HIGH-QUALITY GRADIENT-CORRECTED LINEAR INTERPOLATION FOR DEMOSAICING OF COLOR IMAGES” filed on Mar. 15, 2004 and assigned Ser. No. 10/801,450, an interpolation approach was defined that linearly combines a correction term with an interpolation to obtain a high-quality estimate of a missing pixel color at a pixel within the image. This interpolation technique for demosaicing color images is simple and has a speed similar to that of bilinear interpolation, while producing the high-quality images of more complex techniques. However, the interpolated image quality sometime suffers when interpolation takes place across horizontal and vertical edges, and resulting interpolated images are still subject to artifacts at these points. The artifacts are much attenuated when compared to straight bilinear interpolation, but they can still be noticed in some cases.
Therefore, what is needed is a high-quality interpolation technique that considers correlation among RGB values to improve performance and that is computationally efficient and fast. What is also needed is an interpolation technique that utilizes a larger region of support than bilinear techniques (where the region of support is comparable to that used in nonlinear techniques) for improved quality. What is further needed is an interpolation technique that optimizes the interpolated image, regardless of any edges present in the image. Additionally, what is needed is an interpolation technique that allows for all the color data to be interpolated in one computational pass across the data thereby increasing speed and minimizing computational complexity.